﻿#include <iostream>

static int recurPutIntoBag(const int* itemVolumes, size_t itemSize, int remainCapacity, int index)
{
    if (remainCapacity < 0) return 0;
    if (remainCapacity == 0) return 1;
    if (index > itemSize - 1) return 1;

    int useCur = recurPutIntoBag(itemVolumes, itemSize, remainCapacity - itemVolumes[index], index + 1);
    int notUseCur = recurPutIntoBag(itemVolumes, itemSize, remainCapacity, index + 1);
    return useCur + notUseCur;
}

static int putByStrictTable(const int* itemVolumes, size_t itemSize, int capacity)
{
    int* dp = (int*)malloc(itemSize * (capacity + 1) * sizeof(int));
    memset(dp, 0, itemSize * (capacity + 1) * sizeof(int));

    // dp[index, remain] = dp[index + remain * itemSize]
    for (int i = 0; i < itemSize; i++)
    {
        dp[i] = 1;
    }

    for (int remainCapacity = 1; remainCapacity <= capacity; remainCapacity++)
    {
        for (int index = itemSize - 1; index >= 0; --index)
        {
            int useCur = 0;
            if (index + 1 < itemSize && remainCapacity - itemVolumes[index] >= 0)
            {
                useCur = dp[index + 1 + (remainCapacity - itemVolumes[index]) * itemSize];
            }
            else if (index + 1 >= itemSize && remainCapacity - itemVolumes[index] >= 0)
            {
                useCur = 1;
            }

            int notUseCur = (index + 1 < itemSize) ? dp[index + 1 + remainCapacity * itemSize] : 1;
            dp[index + remainCapacity * itemSize] = useCur + notUseCur;
        }
    }

    int res = dp[capacity * itemSize];
    free(dp);
    return res;
}

// 牛牛准备参加学校组织的春游，出发前牛牛准备往背包中装入一些零食，牛牛的背包容量为w。
// 牛牛家里一共有n袋零食，第i袋零食体积为v[i].
// 牛牛想知道在总体积不超过背包容量的情况下，他一共有多少种零食放法(总体积为0也算一种放法)
int main_PutSnacksIntoBag()
{
    int capacity = 5;
    int itemVolumes[] = { 1,3,2,4,5,4,6 };
    auto itemSize = sizeof(itemVolumes) / sizeof(int);
    int count = recurPutIntoBag(itemVolumes, itemSize, capacity, 0);
    printf("%d\n", count);
    count = putByStrictTable(itemVolumes, itemSize, capacity);
    printf("%d\n", count);
    return 0;
}